7546. Я был везде

Алиса много путешествует по работе. В каждой поездке она посещает один город, прежде чем вернуться домой.

Недавно кто-то спросил её: “Сколько разных городов вы посетили по работе?” К счастью, Алиса вела журнал всех своих поездок. Помогите Алисе определить количество уникальных городов, которые она посетила хотя бы один раз.

Вход. Первая строка содержит количество тестов t (t ≤ 50). Первая строка каждого теста содержит количество поездок n, совершённых Алисой по работе. Следующие n строк описывают сами поездки: i-ая строка содержит название города, который Алиса посетила во время i-ой поездки.

Города, которые посещает Алиса, имеют простые названия: они содержат только заглавные буквы, содержат хотя бы одну букву и не содержат пробелов.

Количество поездок не превышает 100, и каждое название города содержит не более 20 символов.

Выход. Для каждого теста выведите в отдельной строке одно число – количество уникальных городов, которые Алиса посетила во время своих рабочих поездок.

Пример входа	Пример выхода
2 7 saskatoon toronto winnipeg toronto vancouver saskatoon toronto 3 edmonton edmonton edmonton	4 1

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Добавим названия городов из каждого теста в множество строк. Количество посещённых городов будет равно размеру этого множества.

Реализация алгоритма

Объявим строку word и множество строк s.

string word;

set<string> s;

Читаем количество тестов tests. Последовательно обрабатываем tests тестов.

cin >> tests;

while(tests--)

{

Читаем количество городов n. Очищаем множество s.

cin >> n;

s.clear();

Читаем города, добавляем их во множество s.

while(n--)

{

cin >> word;

s.insert(word);

}

Выводим количество различных посещенных городов.

cout << s.size() << endl;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeSet<String> s = new TreeSet<String>();

int tests = con.nextInt();

for(int i = 0; i < tests; i++)

{

int n = con.nextInt();

s.clear();

for(int j = 0; j < n; j++)

{

String word = con.next();

s.add(word);

}

System.out.println(s.size());

}

con.close();

}

}

Python реализация

Читаем количество тестов tests. Последовательно обрабатываем tests тестов.

tests = int(input())

for _ in range(tests):

Читаем количество городов n. Очищаем множество s.

n = int(input())

s = set({})

Читаем города, добавляем их во множество s.

for _ in range(n):

s.add(input())

Выводим количество различных посещенных городов.

print(len(s))